1. Field of the Invention
The present invention relates to a technique for decoding variable-length code words for still images or moving images.
2. Background of the Invention
A method which uses an entropy encoding technique by run length/category encoding and variable-length encoding as one of the compression encoding techniques for still images or moving images is conventionally known well. This technique is employed even in JPEG (Joint Photographic Experts Group) encoding and MPEG-1/-2 (Moving Picture Experts Group) encoding as international standards. In these encoding methods, an event for executing variable-length encoding is caused by implementing entropy encoding by assigning a Huffman code to a two-dimensional event called a run length and level (e.g., Japanese patent Laid-Open No. 2003-115767). The two-dimensional event of run length and level will be referred to as a symbol.
A technique used for moving image compression encoding in recent years that has received a great deal of attention assigns a Huffman code to a three-dimensional event. This technique has already been standardized by an encoding method called H.263 or MPEG-4. As for a three-dimensional event, a “last” significant coefficient in a DCT block called last is taken into consideration in addition to the run length and level used in two-dimensional encoding. For this reason, even when the values of the run length and level are the same, a Huffman code to be assigned changes depending on the last significant coefficient in the DCT block. The three-dimensional event of run length, level, and last will also be referred to as a symbol.
In MPEG-4 encoding, when a symbol is not present in a predetermined Huffman code table, a fixed-length code called an escape is assigned. This also applies to MPEG-1/-2 encoding. In MPEG-4 encoding, when a symbol is not present in a Huffman code table, first, a new symbol is defined by subtracting the value of the maximum level in the Huffman code table from the value of the level of the symbol, and the Huffman code table is searched for again. When it is determined as a result of the search that the symbol is present in the Huffman code table, a corresponding Huffman code is assigned. If the symbol is not present in the Huffman code table, a new symbol is defined by subtracting a value corresponding to (maximum run length in Huffman code table +1) from the value of the run length, and the Huffman code table is searched for again. When it is determined as a result of the search that the symbol is present in the Huffman code table, a corresponding Huffman code is assigned. If the symbol is not present, a fixed-length code is assigned.
FIG. 2 shows a variable-length decoding apparatus corresponding to MPEG-4 encoding, which is disclosed in Japanese Patent Laid-Open No. 2003-115767. A portion corresponding to the block layer of a bitstream encoded by MPEG-4 encoding is input to a queuing means 201. The queuing means 201 includes a shifter circuit. The queuing means 201 sequentially discards a bitstream in accordance with a shift amount requested by an operation control means 207. In the output from the queuing means 201, the start of the code word in a block layer is always queued. The queuing means 201 executes the output operation in synchronism with a clock. The queued code word is input parallel to five blocks, i.e., a DC decoder 202, FLC decoder 203, Huffman table 204, Huffman table ESCR 205, and Huffman table ESCL 206.
The operation control means 207 asserts a DC data output signal to a functional block (not shown) on the output side to indicate that the result of decoding in the DC decoder 202 is effective by a code word when the value of the run length counted by a counter means (not shown) exceeds 64, and the last of symbol data output from a selection means 208 is “1” and indicates that it is the last significant coefficient. In other clock cycle, i.e., when symbol data corresponding to an AC coefficient is decoded, the DC data output signal is negated to indicate that the output of the symbol data signal is effective.
Decoding processing of symbol data corresponding to the AC coefficient is done by the four blocks, i.e., the FLC decoder 203, Huffman table 204, Huffman table ESCR 205, and Huffman table ESCL 206. All Huffman code words, except escape code words of an intra-macro block table B.16 and inter-macro block table B.17, which are described in Annex.B of ISO/IEC14496-2, are registered in the Huffman table 204. For a bitstream input from the queuing means 201, it is determined whether the bitstream coincides with all Huffman code words. If the bitstream coincides with all Huffman code words, corresponding symbol data, Huffman code word length, and a hit signal representing coincidence are asserted.
Even in the Huffman table ESCR 205 and Huffman table ESCL 206, all Huffman code words, except escape code words of the table B.16 and the table B.17 are registered. However, in the Huffman table ESCR 205, an input bitstream is compared with a code word obtained by adding an escape code word +“0” before each Huffman code word, and in the Huffman table ESCL 206, an input bitstream is compared with a code word obtained by adding an escape code word +“10” before each Huffman code word, unlike the Huffman table 204.
The FLC decoder 203 decodes the symbol data when the input bitstream starts with escape code word +“11”. In a code word which starts with escape code word +“11”, a run length, level, and event with a fixed length follow. Hence, the data at a corresponding bit position is directly output as symbol data.
The selection means 208 selects and outputs symbol data and code word length, which are input from an asserted block, in the bit signals parallelly input from the four blocks, i.e., the FLC decoder 203, Huffman table 204, Huffman table ESCR 205, and Huffman table ESCL 206.
When a variable-length encoding apparatus is constructed by hardware, all Huffman code words in the table B.16 and table B.17 are configured by a ROM or hardwired. When the variable-length decoding apparatus shown in FIG. 2 is implemented by hardware, a Huffman table formed from a ROM or hardwired must be prepared in each of the three blocks, i.e., the Huffman table 204, Huffman table ESCR 205, and Huffman table ESCL 206. Hence, the gate scale becomes large.
In a playback apparatus which must execute real-time processing, high-speed decoding processing is required. In this case, a very large load acts on the logic of the output stage from the queuing means 201, and it is therefore difficult to increase the operating frequency. When decoding processing is implemented by software by using a prior art, for a bitstream encoded using the Huffman table ESCR 205, the input code word is compared with all the Huffman table 204, Huffman table ESCR 205, and Huffman table ESCL 206. Since enormous comparison calculation is necessary, real-time decoding can hardly be implemented.